/* Copyright (c) CERN
 * Artistic License 2.0
 */

import java.util.*;
import java.lang.Math;

/**
 * Discrete random variable.
 * This object may be instanciated given samples that do not belong to a discrete distribution.
 * In this case the discrete parts will be extracted.
 * Whether a sample belong to a discrete part depends on the number of other samples close to it
 * and on how close they are.
 *
 * @author Xavier Grehant
 */
public class Discrete {

/**
 * Number of discrete values at most.
 */
   int nbval;

/**
 * discrete values.
 */
   int[] vals;

/**
 * probability that the corresponding discrete value or a higher discrete value is obtained.
 */
   float[] probs;

/**
 * Absolute distance up to which samples are considered occurences of the same discrete value.
 */
   int error;

/**
 * A uniform random number generator.
 */
   Random rand;

/**
 * Constructor
 * @param array the set of samples.
 * @param maxerror distance up to which two samples may be considered 
 *                 two occurences of the same discrete value.
 * @param minprob minimal probability of occurence of a discrete value.
 * @param maxnumber maximum number of discrete values considered.
 *                  Higher values get in first, never mind their priority.
 */
   public Discrete(int[] array, int maxerror, float minprob, int maxnumber) {
      this.error = maxerror;
      rand = new Random();
      nbval = 0;
      vals = new int[maxnumber];
      probs = new float[maxnumber];
      Arrays.sort(array);
      array = flip(array);
      int left = (int) (minprob * array.length);
      int i = left;
      float cumprob = 0;
      while (i < array.length) {
         // todo: make sure the zero values get in.
         // They correspond to continuous values in the initial sample set.
         int right = 0;
         while ((i + right < array.length)
                     && nbval < maxnumber
                     && array[i - left] - array[i + right - 1] <= maxerror)
            right++;
         float prob = (float) (right + left) / (float) array.length;
         if (prob > minprob) {
            vals[nbval] = array[i];
            cumprob += prob;
            probs[nbval] = cumprob;
            nbval++;
            i += right + left - 1;
         }
         i++;
      }
   }

/**
 * This factory method is a default use of the constructor.
 * @return a discrete distribution.
 * @param array the sample set.
 * @param number the maximum number of discrete values.
 */
   public static Discrete createDefault(int[] array, int number) {
      Discrete estimate = new Discrete(array, 0, .05f, number);
      return estimate;
   }

/**
 * This method flips an array of integers.
 * @return flipped array.
 * @param array the array of integers.
 */
   int[] flip(int[] array) {
      int[] result = new int[array.length];
      for (int i = 0; i < array.length; i++)
         result[i] = array[array.length - i - 1];
      return result;
   }

/**
 * Random number generator according to the distribution.
 * @return a random integer according to the distribution.
 */
   public int nextInt() {
      double dice = rand.nextDouble();
      for (int i = 0; i < nbval; i++) {
         if (dice < probs[i]) return vals[i];
      }
      return 0;
   }

/**
 * This method keeps the discrete values of a distribution and replaces the continuous values with 0.
 * @return the resulting array of discrete values and 0 instead of continous values.
 * @param array the array containing the initial values.
 */
   public int[] cleanOut(int[] array) {
      Arrays.sort(array);
      array = flip(array);
      float probContinuous;
      if (nbval == 0) probContinuous = 1;
      else probContinuous = 1 - probs[nbval - 1]; // the prob of last value is the sum of all discrete value probabilities
      int size = (int) ((float) array.length * probContinuous);
      int[] result = new int[size];
      int i = 0, j = 0, k = 0;
      while (i < array.length && j < nbval) { // spanning all discrete values
         while (i < array.length && k < size && array[i] > vals[j]) { // fill before discrete value
             result[k] = array[i];    
             i++; k++;
         }
         while (i < array.length && array[i] >= vals[j] - error) { // skip discrete value occurences
             i++;
         }
         j++;
      }
      while (i < array.length && k < size) { // fill with remaining lower than lowest discrete value
         result[k] = array[i];
         k++; i++;
      }
      return result;
   }
}

